The present invention relates generally to the field of computer software optimization. More particularly, the present invention relates to a method for practical concurrent copying garbage collection offering minimal thread blocking times.
The popularization of the World Wide Web has exacerbated a problem for software developers trying to create software for networked consumer devices. While millions of people around the globe are surfing the Internet and browsing web pages with their computers, not all of those computers are the same. One person may be using a Macintosh, another a PC, and yet another user a UNIX machine. Hence software developers may find it desirable to design computer programs that could support multiple host architectures and could allow secure delivery of its software components.
The Java programming language and environment is designed to meet the challenges of application development in the context of heterogeneous, network-wide distributed environments. A program written in the Java Language compiles to a bytecode file that can run wherever a Java Platform is present. This portability is possible because at the core of a Java Platform is a Java Virtual Machine. Java bytecodes are designed to operate on a Java Virtual Machine (VM). The Java Virtual Machine is an abstract computing machine that has its own instruction set and uses various memory areas.
FIG. 1 is a block diagram of the elements in a client computer system 100 equipped to interpret and compile Java class files. The client computer system 100 includes computer hardware 110 controlled by an operating system 120. The computer hardware further comprises of computer memory 112 and machine registers 114. The system 100 also includes a Java VM implementation 130 for executing code contained in Java class files 160.
In a networked environment, a user would first access a computer server through the network and download the desired Java class file(s) 160 into a client computer system 100. After each Java class file has been verified, the interpreter 132 begins interpreting the Java bytecodes of the class file 160 and thus the code is executed.
Alternatively, a Java xe2x80x9cJust-In-Timexe2x80x9d (JIT) compiler 134 compiles the Java class file and generates compiled Java code 140 in the form of native processor code. The compiled Java code 140 is directly executed on the computer hardware 110. In order to maintain the state of the Java VM 130 and make system calls, the compiled Java code 140 may make calls 150 into the Java VM 130. Likewise, the Java VM 130 calls 150 compiled Java code 140 to cause it to execute on the computer hardware 110.
Java was derived from the C++ programming language. Java includes some other important features from garbage collected languages (e.g., Smalltalk and LISP)xe2x80x94including automatic memory storage management. Garbage collected languages, such as Java, allow the system (garbage collector) to take over the burden of memory management from the programmer. When a program runs low on heap space, the garbage collector (GC) determines the set of objects that that program may still access. Objects in this set are known as live objects. The space used by objects that will no longer be accessed (xe2x80x9cdead objectsxe2x80x9d) is freed by the garbage collector for future use. An object is defined as a collection of contiguous memory locations, lying in a single region that can be addressed and accessed via references.
A reference, also called a pointer, is the address of an object. Objects do not overlap and may be relocated independently of one another by the collector. In some cases, an object corresponds to a Java object. Multiple low-level objects may also be used to represent a single Java object. One example of this is a Java object with complex monitor locking happening. An object may contain slots, non-slot data, or both. A slot is a memory location that may contain a reference (pointer) to an object. A slot may also refer to no object, i.e., contain the null pointer. Memory locations can be categorized into slots and non-slot data correctly and unambiguously.
FIG. 2A is a diagram of CPU activity in a multiprocessor system using a traditional garbage collection algorithm. The horizontal axis represents time while the vertical axis represents the useful application work. In traditional garbage collection algorithms, all of the threads have to stop. The garbage collector runs, performing garbage collection, and then the threads start up again. Hence there are large blocks of time when none of the CPUs is performing useful work and only one of the CPUs is doing the garbage collection work. The actual useful or mutator work is suspended. In FIG. 2A, the threads on CPU0 through CPU3 are suspended for time xe2x80x9cZxe2x80x9d while the garbage collector is running on CPU0. The threads are blocked during garbage collection. Furthermore, threads can not be resumed until the garbage collection completes. The application threads resume execution when garbage collection stops. The thread stoppage may not appear dramatic in a system with a small number of processors. But in a multiprocessor computing system with eight or sixteen processors, the performance loss becomes an issue.
There are many algorithms for performing garbage collection. All the algorithms start with a set of roots that enumerate all objects in the heap that are directly reachable. A root is a slot whose referent object (if any), is considered reachable, along with all objects transitively reachable from the referent. The remaining objects in the heap are unreachable and can be reclaimed. One type of garbage collection is called conservative, or ambiguous roots, garbage collection. In conservative garbage collection, the garbage collector assumes all global variables, in registers or on the stack, are root slots even though some might hold integers, or floating point or string data. Another type of garbage collection is precise garbage collection. In precise garbage collection, the root set must unambiguously contain all reference values, or else memory errors will result. This is because precise garbage collection compacts the memory space by moving all the objects it finds to another memory region. The values in the root set must contain reference values since the garbage collector copies and moves the objects pointed to by references, and then updates the references correspondingly. If a value is mistakenly considered a reference value when it is not, a wrong piece of data will be moved, and/or a non-reference mistakenly modified, and program errors may occur.
Previous concurrent collection algorithms overlap some parts of collection with mutation, but still stop the world to xe2x80x9cflipxe2x80x9d (adjust, correct) all the mutator stacks and roots. A mutator thread performs application work. In a large server application, where there are perhaps hundreds of threads, thread stack flipping time can introduce unacceptable pauses.
A method for practical concurrent copying garbage collection offering minimal thread blocking times is described. The method comprises achieving dynamic consistency between objects in an old memory space and objects in a new memory space. Threads are allowed to progress during garbage collection and threads are flipped one at a time. No read barrier is required.
Other features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below.